package com.kehao.leetcode.hard.array;
/*
给你一个长度为n的整数数组nums，其中n > 1，返回输出数组output，其中 output[i]等于nums中除nums[i]之外其余各元素的乘积。
1. 不能用除法/
2. 时间复杂度为O(n)
 */

import org.junit.Test;

import java.util.Arrays;

public class ProductExceptSelfSolution {

    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        result[0] = 1;
        for (int i = 1; i < result.length; i++) {
            result[i] = result[i-1]*nums[i-1];
        }
        int right =1;
        for (int i = result.length-2; i>=0 ; i--) {
            right*=nums[i+1];
            result[i] = result[i]*right;
        }
        return result;
    }

    @Test
    public void test01(){
        int[] num = {1,2,3,4};
        Arrays.stream(productExceptSelf(num)).forEach(i-> {
            System.out.print(i);
            System.out.println();});
    }

}
